Slide 5

The Formal Definition of a Tree

A tree is a non-linear data structure defined by a set of rules.

Nodes and Edges

A tree $T$ is a pair $(V, E)$, where $V$ is a set of nodes (vertices) and $E$ is a set of edges.

The Root

There is a unique node $r \in V$ called the root, which has no parent.

Parent-Child Relation

Every node $v \in V \setminus \{r\}$ has exactly one parent node $u$.

Properties

The graph is connected and acyclic. A tree with $n$ nodes has $n-1$ edges.

Live Rule Check

One root node
One parent per non-root node
The graph must be connected
Cannot contain cycles

Actions